人工智能算法导论 Lecture Notes: Chapter3 一般学习模型

南开大学数院《人工智能算法导论》课程笔记, 任课老师张胜（https://my.nankai.edu.cn/sms/zs/list.htm）。如有错误，或语言流利度的改进建议，欢迎私信。带*的地方是自己补充的内容，老师没讲。

定义（PAC可学习, PAC-learnable）我们称一个概念类/学习任务是PAC可学习的, 若存在一个学习算法和函数, 使得对任意, 和上任何一个分布, 任意的标记函数（概念）, 如果满足可实现性假设, 那么当样本容量时, 算法将以不小于的概率返回一个假设使得

则我们称假设类将会以的概率近似正确(). 当上述算法存在的时候, 我们称其为一个概念类/学习任务的PAC学习算法.

❝
在上一节最后的定理中, 对于足够大的样本容量, 由规则生成的有限假设类将会以最少的概率近似正确.
注
准确度参数表征输出的分类器和最优的分类器之间的距离（对应于“近似正确”部分）；置信参数的变换表征分类器达到准确度要求的可能性（对应“概率”部分）.
这些近似在实际应用中是不可避免的. 由于训练集是随机生成的, 始终有可能发生样本不提供足够信息的小概率事件情况. 更进一步, 即使我们足够幸运, 能够得到一个具有很好代表性的训练样本集, 由于其为有限样本, 因此的很多细节依然不能被反映出来. 精度参数允许学习分类器产生小的误差.
“学习任务”这个词可以看成概念类的一般化, 表示在数据彰显的所有可能的规律中寻找符合数据特点的规律. 在二分类以外的“一般的分类问题”、“回归问题”等问题中, 我们会用“学习任务”来表述可学习性.

3.2 采样复杂度（样本复杂度）

定义（采样复杂度/样本复杂度）函数决定学习假设类的样本复杂度. 我们定义假设类的采样复杂度（或样本复杂度, 与, 都有关）为满足PAC可学习条件的最小整数, 记为.

❝
例
对有限假设类, 由上一个章节最后一个定理, 其PAC可学习的样本复杂度为
其中""为上取整符号. 在时, 模型难以过拟合.
在去掉可实现性假设的时候，假设类的样本复杂度定义为满足不可知PAC可学习的最小整数，也记为. 不可知PAC可学习的定义见3.5节。

3.3 更常见的学习模型

尽管在上面的一些假设下, 我们有很高的概率可以避免模型的过拟合, 但假设

❝
假设类满足可实现性假设；
标签集合, 只适用于二分类问题；
标签完全由特征决定
......

很多, 理论适用的范围仍然过于狭窄. 所以我们考虑下面的推广（泛化）：

❝
放宽可实现性假设：对实际应用, 可实现性假设可能太严格了（难以判断或验证成本太高）；
学习问题不只是二分类问题.

3.3.1 放宽可实现性假设——不可知PAC学习

❝
可实现性假设要求, 使得
即.

但在很多实际问题中, 该假设可能难以判断或验证, 甚至有可能不成立.

此外, 最好不要假设标签完全由我们假定的特征决定.

❝
例在芒果二分类的问题中, 两个相同颜色、相同软硬程度的芒果可能味道并不相同.

因此我们可以将标记函数替换为更加灵活的概念：数据标签生成分布.

定义（数据标签生成分布）形式上, 我们将试验的数据标签生成分布定义为上的概率分布（即定义域和标签集上的联合分布）, 仍用表示. 可将其分解为两部分：

未标记定义域点的概率分布（也称为边缘分布）；
每个定义域点标记的条件概率分布.

❝
例在芒果二分类🥭的例子中, 边缘分布决定碰到某个芒果的概率；而条件概率分布表示的颜色和软硬程度对应芒果“不好吃”、“好吃”的概率.

改进后的训练误差和泛化误差

对上的概率分布, 根据分布随机生成带标签的数据点, 定义预测器的泛化误差（真实误差）为

我们希望找到使得上述误差最小话的预测器. 然而学习器并不知道数据生成分布的信息, 学习器知道的是训练集. 训练误差（经验风险、经验误差）仍然定义为

给定, 对任意我们都可以计算. 则在没有可实现性假设（即存在泛化误差为0的预测器）的时候, 我们希望寻找预测器使得真实风险（泛化误差）最小.

改进后的样本误导集

回顾可实现性假设成立的时候，样本误导集的定义：“

”, 我们发现样本误导集描述了“对应训练误差误导了我们（偏离了真实的泛化误差）的样本集”。因此，在可实现性假设不成立的时候，不一定为，样本误导集的更加一般的定义如下：

定义（样本误导集）可实现性假设不一定成立的时候，样本误导集为.

贝叶斯最优预测器

定义（贝叶斯分类器）给定上的任意数据标签生成分布, 将映射到的贝叶斯分类器（记为）为

命题对于任意的概率分布, 贝叶斯分类器是最优的, 即对任意的其他分类器, 有.

❝
证明事实上, 一方面
另一方面,
因此我们记, , , , 则
.
故
故, 我们有
故原命题得证.
评注证明思路的关键在于对两个泛化误差的事件集进行合理的拆分, 以及把问题的本质（一个多元不等式）提取出来. 在最后一个等价的推导的时候, 我们通过尝试代入来验证不等式的成立性及寻找思路.

可惜我们不知道概率分布, 故无法使用这个最优分类器. 学习器只能从训练样本中获取信息.

显然, 我们不能期望学习算法给出一个真实误差小于最小可能误差的预测器. 可以证明, 如果对数据生成分布不做先验假设, 没有算法能够保证找到一个和贝叶斯最优分类器一样好的预测器. （后面会证明这个结论）

当然, 我们希望学习算法能够找到一个预测器, 其误差与贝叶斯最优预测器（没有可实现性假设的时候“最好”的预测器）的误差相差不大. 这时“PAC(Probably Approximately Correct)可学习”的对应概念如下：

不可知PAC可学习

定义（不可知PAC可学习）我们称一个概念类/学习任务是不可知PAC可学习的, 若存在函数和一个学习算法, 使得对任意, 和上的任何分布, 当样本容量时（其样本由分布独立同分布采样得到）, 算法将以不小于的概率返回一个预测器, 使得

❝
注
“不可知”指的是最优预测器不可知. 这里是在找与泛化能力最强的预测器无限接近的预测器.
这里没有可实现性假设, 故, 学习器不能保证任意小的误差. 但即使和假设类中最好的预测器有些许差距, 学习器依然可以认为学习成功.
若满足可实现性假设, 则, 此时即为PAC可学习. 故不可知PAC可学习是PAC可学习的一种泛化（推广）.

3.3.2 学习问题的建模

我们将模型进一步拓展以应用到更广的学习任务.

(1).多分类问题

❝
例文本分类问题：将文本按其主题进行分类（如新闻、体育等）, 可将文档用一系列的特征来表示, 特征可以是文档中不同关键词出现的频数或其他相关特征（文档的大小以及来源）. 在这个任务中, 标签集是所有可能主题的集合（可以是任意大的有限集）. 确定了定义域和标签集后, 主体框架的其他部分和芒果例子相似.
预测器的损失函数就是
其中

(2).回归问题

在这类问题中, 我们希望找到数据的简单模型——数据集和数据集之间的关联函数.

❝
例根据超声波检测到的婴儿的头围、腹围和股骨长度预测婴儿的体重.
在这个任务中, 定义域是（三个超声波检测量）的一个子集（可以近似看成三个区间的笛卡尔积）, 值域是.

训练集为有限序列对, 输出为从的预测函数.

度量是否成功, 可以用范数平方的期望来评估：

我们称之为（分类问题的）损失函数.

类似二分类问题, 我们还能用PAC可学习等理论框架解释上面两类问题.

3.4 广义损失函数

我们发现, 分类问题和回归问题所用的损失函数形式上不同. 下面“广义损失函数”的概念的提出就是为了统一各个损失函数的形式.

定义（广义损失函数、泛化误差、经验误差）给定任意假设集（到的一族函数）和定义域（监督学习是, 无监督学习是, 下面的与此处同义）, 令为到非负实数集合的一个映射, 称之为广义损失函数(generalized loss function). 我们将此时的泛化误差定义为（从分布随机采样）

其中, 上的概率分布为. 定义预测器在训练集下的经验误差（或训练误差）为

❝
注在不引起混淆的情况下, 我们在称呼时会把“广义”两字去除.

分类和回归问题的损失函数

不同的问题和对应的需求对应着不同的广义损失函数. 下面我们介绍几种常见的广义损失函数：

损失函数

, 损失函数

这种损失函数用于二分类或多分类任务.

平方损失函数
, 损失函数
这种损失函数适用于回归问题.

这两种损失函数通常用于监督学习任务, 其中需要有标签（或目标值）来评估模型的性能. 在无监督学习中, 通常没有标签或目标值可供使用, 因此这些损失函数不太适用于无监督学习.

无监督学习的目标通常是发现数据中的结构、模式或特征, 而不需要预测目标变量. 因此, 无监督学习任务通常涉及使用不同类型的目标函数或评估指标, 例如聚类算法中的簇内距离.

3.5 广义损失函数下的不可知PAC可学习

下面是广义损失函数下的不可知PAC可学习的定义. 顾名思义，下面的定义旨在刻画下面的情况：

❝
在不知道最优预测器 (满足) 的前提下，某种任务是可以学习的.

定义（不可知PAC可学习）给定一个集合上的学习任务和广义损失函数, 若存在一个函数和一个学习算法, 对任意, 以及上的任何分布, 当样本容量时（样本由分布独立同分布采样得到. 注意, 这里若是监督学习, 则分布为样本和标签的联合分布, 换句话说是带标签的样本的分布）, 算法将以不小于的概率返回一个预测器使得

其中, 是广义损失函数. 则我们称该学习任务是不可知PAC可学习的.

❝
注对任意给定的, 由于要取期望，所以我们将视为随机变量, 故是可测的. 即, 集合 ,其中是概率空间中的事件-代数. 这里我们假设这样的存在, 且.
例在二分类问题中, 损失函数为. 对于任意的, 概率空间上的事件-代数是的一个子集族, 包含集合
, .

3.6 学习过程的一致收敛性

3.6.1 一致收敛是（不可知PAC）可学习的充分条件

已知一个假设类, ERM学习任务的工作流程如下：接收训练样本集, 学习器评估每一个中的对于已知样本的损失（误差）, 并输出中的一个最小化经验风险的元素.

定义（-代表性样本集）如果满足,

则称训练集为 -代表性样本集（关于定义域, 假设类, 损失函数和分布）.

❝
注如果把“ERM学习”类比为“炒菜”, 则“”可以看作炒菜中的“食材”. 如果我们知道-代表性样本集, 则我们就可以找到充分代表样本集的集合（用训练误差代表泛化误差）.

下面的定理表明了用代表性样本集去训练模型（找满足ERM规则的预测器）的好处：此时模型泛化误差是小的.

定理设训练集是-代表性的（关于定义域, 假设类, 损失函数和分布）, 那么任何一个的输出, 都满足

❝
证明对,
所以
注
如果把“ERM学习”类比为“炒菜”, 则“根据训练输出”可以看作炒菜中的“烹饪流程”.
定理表明, 为了确保ERM规则下的学习任务是不可知PAC可学习的, 我们应该满足至少在概率下随机选择的训练集是-代表性的（从而输出的满足）.

下面的定理说明了训练样本集容量足够大的时候，有大概率“趋于”代表性样本集，大概率能代表整个样本。

定义（一致收敛性质）如果一个假设类（关于定义域和损失函数）满足存在一个函数, 使得

和上所有概率分布, 若训练样本集，满足, 则当样本容量时, 至少在概率下是-代表性的。

此时我们称假设类具有一致收敛性质. （上标指的是uniform convergence）

❝
注
注意品味“衡量集合代表性的最小样本容量”跟“衡量PAC可学习的样本复杂度”的不同。
一致性指的是对定义域中所有可能的概率分布和所有中的元素，有一个一致的最小样本容量，使得此容量以上的代表性强。
我们发现，的时候，在至少概率是代表性的。从而结合上一个定理我们可知，ERM规则返回的有的概率泛化误差是小的，满足

定理如果假设类关于函数有一致收敛性质, 那么的时候，

学习任务是不可知PAC可学习的；
若记的样本复杂度为，则.

❝
证明
由上面的第二个注释可以得证；
事实上，由于的样本复杂度是使学习任务满足不可知PAC可学习的最小样本量，故.

3.6.2 （一定条件下）有限假设类是不可知PAC可学习的

对有限假设类, 如果我们能够证明其具有一致收敛性质（可以近似地理解为）, 那么每个有限假设类都是不可知PAC可学习的.

下面我们证明一个定理，其说明了给损失函数一定条件的时候，一致收敛性质可以被证明。

定理设为一个有限假设类, 为定义域, 为损失函数（注意值域）, 则

假设类关于函数具有一致收敛性质；

❝
即, 任何概率分布, 至少在概率下, 从中采样得到的独立同分布样本构成的训练集, 对所有有成立。

且成立

证明首先，我们去找样本容量使得下面的一致收敛性质成立：对, 任何概率分布, 至少在概率下, 从中采样得到的独立同分布样本构成的训练集, 对所有有成立. 即

也即

❝
这里内部的集合是样本误导集。

由于

故由可列可加性,

❝
分析我们的目标是放缩上面的式子，因此我们把, 拆开来分析。
由以及, 故有, .
从而由
可知
从而是随机变量与其期望之间的偏差.
由有限（）以及大数定律, 经验平均值收敛到其数学期望, 即
但大数定律仅仅代表一个渐进结果. 但事实上样本容量有限, 不会趋于无穷, 上面的结论对于任意给定有限样本容量的训练集, 无法提供任何信息.

因此我们提出下列引理：

❝
引理（Hoeffding不等式）令是i.i.d.的随机变量. 且假设对于, , . 那么对于所有,
引理的证明 见 https://en.wikipedia.org/wiki/Hoeffding%27s_inequality 。

记随机变量为, 由于是给定的, 而独立同分布, 故也独立同分布. 且

设的范围为, 则. 从而

故

如果如定理所示, 选择样本容量（这个界就是由上式解出来的）, 则有

一致收敛性成立。而由的定义，

定理得证.

❝
注
把损失函数的值域设置为是因为证明中用到了Hoeffding不等式。
由上述定理和“由假设类一致收敛知学习任务是不可知PAC可学习的”立刻得到推论：
推论记假设类的样本复杂度为, 则.
虽然此定理只适用于有限假设类，但有一个简单的离散化技巧可以让我们得到无限假设类的实际样本复杂度的一个好的估计。考虑一个假设类由个参数来参数化。
例令, , 假设类是所有形如
的函数，则每个假设都可以用一个参数参数化。显然，取遍, 这是一个无限假设类。然而，如果打算用计算机实际学习这个假设类，我们可以用浮点表示法来表示实数（如64位二进制浮点数）。若我们用64位二进制浮点数表示的集合来参数化假设类，则最多有个这样的数, 假设类的实际大小为.
更一般地, 如果假设类中的每个假设需要用个64位二进制浮点数数来参数化, 实际上我们学习的是一个最大为的假设类. 由上述定理的推论可知, 其样本复杂度的一个上界为.